[AGC022E]Median Replace

2019-12-11
#动态规划Dp #AC自动机
Atcoder

题意

对于长度为奇数的01?字符串，可以将连续3个字符用中位数代替，问使得最后可以变为1的方案数

题解

手动建自动机，表示字符串的替代转移

可以发现替换掉的0越多越好，所以可以贪心地转移，自动机节点数有限

注意，在建立自动机的时候，有些节点（如2，5）要用后两个字符再去匹配，有可能它们和后面的字符消去，形成更优的解

自动机的样子盗张图

倒序Dp即可

调试记录

无

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 3e5 + 5;
const int mo = 1e9 + 7;
const int to[8][2] = {3, 1, 5, 2, 2, 2, 4, 7, 3, 3, 6, 1, 5, 5, 3, 1};
int f[maxn][8], n; char str[maxn];
int main(){
	scanf("%s", str + 1); n = strlen(str + 1);
	f[n + 1][1] = 1, f[n + 1][2] = 1;
	for (int i = n; i >= 1; i--)
		for (int j = 0; j < 8; j++){
			if (str[i] != '0') f[i][j] += f[i + 1][to[j][1]];
			if (str[i] != '1') f[i][j] += f[i + 1][to[j][0]];
			f[i][j] %= mo;
		}
	printf("%d\n", f[1][0]);
	return 0;
}

参考资料：link